home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / pascal / sort_stm.zip / SINDEXED.PAS next >
Pascal/Delphi Source File  |  1992-10-18  |  18KB  |  627 lines
  1. {---------------------------------------------------------------------------}
  2. {                AUTHOR: Bruce Ruona, FIDONET: 1:2280/1 }
  3. {               Released into Public Domain, October 1992}
  4. {}
  5. {                          October 18th, 1992}
  6. {VERSION 1.01 implements folloing changes from previous editions:}
  7. {   EOS: End of stream function in Base stream type}
  8. {}
  9. {   NDXSTREAM: maintains a listing of OFFSETS into MASTER stream}
  10. {              by storing a series of LONGINTs onto an EMS stream}
  11. {              Uses a simple BINARY INSERTION method to speed up search}
  12. {              of current data}
  13. {}
  14. {   SORTEDINDEXSTREAM: over-ride GET method to use NDXSTREAM offset}
  15. {                      ITEMPOS method to position to specified ITEM #}
  16. {                      DONE Destructor over-ride to also dump Ndxstream}
  17. {                      A few other necessary new procs/methods also added}
  18. {}
  19. { BENCHMARKS: now creates and stores in excess of 1,200 base objects/Minute}
  20. {             maximum Search on any Insertions: 8.6 times AVG.}
  21. {---------------------------------------------------------------------------}
  22. {}
  23.  
  24. Unit Sindexed;
  25. {Provides a searchable/Indexed & Searchable Stream}
  26.  
  27. Interface
  28.   Uses Dos,
  29.        Crt,
  30.        Objects;
  31.  
  32. Type
  33.    {our Base type for all searchable objects}
  34.    {all Searchable objects must be derived from this!}
  35.    pIndex = ^indexobj;
  36.    IndexObj = OBJECT(Tobject)
  37.       {compare testobj against current for equality}
  38.       {base object calls ABSTRACT error if called!!}
  39.       Function Compare(T: pIndex): INTEGER;            VIRTUAL;
  40.    end;
  41.  
  42.    {a searchable stream that Knows a file name, INIT will load data to stream}
  43.    {from file name, DONE will dump data back to file}
  44.    pIndexed = ^indexedstream;
  45.    IndexedStream = OBJECT(tEmsStream)
  46.       FileName: Pstring;
  47.       ItemCount: Longint;   {count of Items in stream}
  48.       Constructor Init(amin: Longint; fname: Pathstr);
  49.       Destructor Done;                                  VIRTUAL;
  50.       Procedure Flush;                                  VIRTUAL;
  51.       Function  Find(SearchObj: pIndex): Boolean;       VIRTUAL;
  52.       {over-ride Put to provide mangement of ITEMCOUNT variable}
  53.       Procedure Put(P: pObject);
  54.       {Identical to EOF function for Files}
  55.       Function EOS: Boolean;                            VIRTUAL;
  56.    end;
  57.  
  58.     {User definable STATUS display for call to ndxstream.Reindex method,}
  59.     {which may take a minute or two to complete}
  60.     NdxDisplayProc = Procedure(CurrPos:LongInt;Col,Row: Byte);
  61.  
  62.    {a Descendent of tEMSStream, provides a sorted list of offsets into}
  63.    {master stream allowing easy searches by using a BINARY Insertion method}
  64.    {and storing a simple list of LONGINT's on stream}
  65.    pNdxStream = ^NdxStream;
  66.    NdxStream  = OBJECT(tEMSStream)
  67.       owner: pIndexed; {a pointer back to our master stream note pointer to ANCESTOR}
  68.       CP: Longint; {Current ITEM NUMBER of Master index}
  69.       fname: pathstr; {File name for saving index}
  70.       displayProc: NdxDisplayProc; {Procedure to call on REINDEX Routine}
  71.       Constructor Init(master: pStream; Amin: longint; NdxFile: Pathstr);
  72.       Destructor Done;                                          VIRTUAL;
  73.       Function EOS: Boolean;
  74.       {rebuild our index from Scratch}
  75.       Procedure Reindex;
  76.       {inserts a new key into stream}
  77.       Procedure Insert(Key: Pindex; KeyPos: LongInt);
  78.       {searches for KEY in master stream using offsets}
  79.       Function Search(Key: pIndex; VAR AtPos: LongInt): Boolean;
  80.       {returns total number of Items in list, from 0 to N+1}
  81.       Function Count: Longint;
  82.       Function At: Longint; {returns OFFSET of CP [Current item]}
  83.       {updates CP for SEEK activity on MASTER LIST}
  84.       Procedure Pos(P: longInt);
  85.       {updates CP for GET activity on Master List}
  86.       Procedure NextPos;
  87.       {Dump index to named file}
  88.       Procedure Flush;                                           VIRTUAL;
  89.    end;
  90.  
  91.  
  92.    {a descendent of indexedstream that inserts data into a sorted order based}
  93.    {on result of pindex compare method, NOte that the ITEMPOS method should}
  94.    {be used in the main program in place of SEEK especially to reset to beg.}
  95.  
  96.    pSortedIndex = ^SortedIndexStream;
  97.    SortedIndexStream = Object(IndexedStream)
  98.        indexList: pNdxStream;
  99.        Constructor Init(amin: Longint; fname: Pathstr);
  100.        Destructor Done;                                 VIRTUAL;
  101.        Procedure Insert(Key: pIndex);
  102.        Function  Find(SearchObj: pIndex): Boolean;      VIRTUAL;
  103.        Function Get: pObject;                           VIRTUAL;
  104.        {similar to SEEK but seeks to ITEM Number instead of OFFSET}
  105.        Procedure ItemPos(ItemNum: Longint);
  106.        {simply provides a calling point for INDEXLIST reindex method}
  107.        Procedure Rebuild;
  108.        {Simply returns COUNT from IndexList}
  109.        Function Count: Longint;
  110.    end;
  111.  
  112. implementation
  113.  
  114. {our base object COMPARE procedure}
  115. Function IndexObj.Compare(T:pIndex): Integer;
  116. begin
  117.    Abstract;         {call ABSTRACT error procedure if called!}
  118. end;
  119.  
  120. {a procedure to call to display status during a lengthy REINDEX call}
  121. {$F+}
  122. Procedure OurDisplayProc(CurrPos: Longint;Col,Row: Byte);
  123. begin
  124.    Gotoxy(Col,Row);
  125.    Write('REINDEXING:...',Currpos:8);
  126. end;
  127. {$F-}
  128.  
  129. {=========================================================================}
  130. { Indexstream                                                             }
  131. {=========================================================================}
  132.  
  133. CONSTRUCTOR IndexedStream.Init(Amin: Longint; Fname: Pathstr);
  134. Var TmpStream: tBufStream;
  135.     InitSize: Longint;
  136. begin
  137.    tEmsStream.Init(Amin,MaxLongInt);
  138.    if (Fname='') or (status<>StOK) then
  139.      FAIL
  140.    else
  141.    begin
  142.       FileName:=NewStr(Fname);
  143.       ItemCount:=0;
  144.       TmpStream.INIT(Fname,STOpen,8*1024);
  145.       if TmpStream.Status=STOK then
  146.       begin
  147.          InitSize:=TmpStream.Getsize;
  148.          Seek(0);                  {position our stream...}
  149.          TmpStream.Seek(0);        {position temp stream to start}
  150.          copyfrom(Tmpstream,initsize);
  151.          ItemCount:=0;
  152.          Seek(0);
  153.       end;
  154.       tmpstream.done;
  155.    end;
  156. end;
  157.  
  158. DESTRUCTOR IndexedStream.Done;
  159. begin
  160.    Flush;   {save EMS back to file}
  161.    if Filename<>NIL then
  162.      disposeStr(filename);
  163.    tEmsStream.done;
  164. end;
  165.  
  166. {Flushes our EMS stream back to named DISK file}
  167. PROCEDURE IndexedStream.Flush;
  168. var BUFF: tBufStream;
  169. begin
  170.    buff.Init(Filename^,stCreate,8*1024);
  171.    if Buff.Status=StOK then
  172.    begin
  173.       Seek(0);
  174.       Buff.CopyFrom(Self,GetSize);
  175.    end;
  176.    buff.done;
  177. end;
  178.  
  179. {Searches Stream for object Searchobj, returns FALSE if NOT found}
  180. Function IndexedStream.Find(SearchObj: Pindex): Boolean;
  181. VAR Temp: pIndex;
  182.     found: Boolean;
  183. begin
  184.    seek(0);
  185.    Found:=False;
  186.    while (GetPos<GetSize) and NOT FOUND do
  187.    begin
  188.      Temp:=Pindex(get);
  189.      if (Temp<>NIL) AND (Temp^.Compare(Searchobj)=0) then
  190.      begin
  191.         if Temp<>NIL then
  192.            Found:=TRUE;
  193.      end;
  194.      if Temp<>NIL then
  195.        dispose(Temp,done);
  196.    end;
  197.    Find:=Found;
  198. end;
  199.  
  200. Procedure IndexedStream.Put(p: pObject);
  201. begin
  202.    tEmsStream.Put(p);
  203.    inc(ItemCount);
  204. end;
  205.  
  206. Function IndexedStream.EOS: Boolean;
  207. {returns TRUE if at _End _Of _Stream}
  208. begin
  209.    EOS:=(GetPos>=GetSize)
  210. end;
  211.  
  212. {=========================================================================}
  213. {  SortedIndexStream                                                      }
  214. {=========================================================================}
  215. Constructor SortedIndexStream.Init(amin: Longint; fname: Pathstr);
  216.  
  217. {compute NDX name for associated index file based on passed fname}
  218. Function IndexName: PathStr;
  219. VAR DS: DirStr;
  220.     NS: NameStr;
  221.     Es: Extstr;
  222. begin
  223.    if FName<>'' then
  224.    begin
  225.       Fsplit(Fname,Ds,Ns,Es);
  226.       IndexName:=DS+NS+'.NDX';
  227.    end
  228.    else IndexName:='TEMP.NDX';
  229. end;
  230.  
  231. begin
  232.    IndexedStream.Init(amin,fname);
  233.  
  234.    IndexList:=NIL;
  235.    ItemCount:=0;
  236.  
  237.    if Status<>StOK then FAIL else
  238.    begin
  239.       {initialize our Base index list with a 64K EMS Buffer}
  240.       IndexList:=NEW(pNdxStream,INIT(@Self,64*1024,IndexName));
  241.       if (IndexList=NIL) or (IndexList^.Status<>StOK) then FAIL;
  242.       if Count<>0 then begin;end; {just to set our ITEMCOUNT var.}
  243.    end;
  244.  
  245. end;
  246.  
  247. Destructor SortedIndexStream.Done;
  248. begin
  249.    {dispose of Indexlist, and dump index list to computed named file}
  250.    if IndexList<>NIL then
  251.       Dispose(indexList,Done);
  252.    IndexList:=NIL;
  253.    IndexedStream.Done;
  254. end;
  255.  
  256. Procedure SortedIndexStream.Insert(Key: pIndex);
  257. VAR P: Longint;
  258. begin
  259.    P:=GetSize;
  260.    Seek(GetSize);  {Appending at end of file}
  261.    Put(Key);
  262.    if IndexList<>NIL then
  263.      IndexList^.Insert(Key,P);
  264. end;
  265.  
  266. {Search method, only searches until found or item>Searchobj}
  267. Function  SortedIndexStream.Find(SearchObj: pIndex): Boolean;
  268. VAR Temp: pIndex;
  269.     found: Boolean;
  270.     Result: Integer;
  271.     P: Longint;
  272. begin
  273.    ItemPos(0);
  274.    Found:=False;
  275.    Find:=IndexList^.Search(SearchObj,P);
  276. end;
  277.  
  278. Function SortedIndexStream.Get: pObject;
  279. begin
  280.    Get:=NIL;
  281.    {get offset of IndexList CP, and postion Stream to point}
  282.    if IndexList<>NIL then
  283.        seek(IndexList^.At);
  284.  
  285.     {end of stream?}
  286.    if NOT EOS then
  287.    begin
  288.       Get:=IndexedStream.Get;
  289.       if IndexList<>NIL then
  290.       begin
  291.          IndexList^.NextPos;
  292.          if IndexList^.At<=GetSize then
  293.             seek(IndexList^.At)
  294.          else
  295.             Seek(GetSize);
  296.       end;
  297.    end;
  298. end;
  299.  
  300. Procedure SortedIndexStream.ItemPos(ItemNum: Longint);
  301. begin
  302.    if IndexList<>NIL then
  303.    begin
  304.       if ItemNum<IndexList^.COUNT then
  305.         IndexList^.CP:=ItemNum;
  306.       Seek(IndexList^.At);
  307.    end
  308.    Else seek(GetSize);
  309. end;
  310.  
  311. Procedure SortedIndexStream.Rebuild;
  312. begin
  313.    If IndexList<>NIL then
  314.      IndexList^.Reindex;
  315. end;
  316.  
  317. {Updates ItemCount, and provides direct call into indexlist.count}
  318. Function SortedIndexStream.Count: Longint;
  319. begin
  320.    If IndexList<>NIL then
  321.      ItemCount:=IndexList^.count
  322.    else
  323.      ItemCount:=-1;
  324.    Count:=ItemCount;
  325. end;
  326.  
  327. {=========================================================================}
  328. {  NdxStream Methods                                                      }
  329. {=========================================================================}
  330. Constructor NdxStream.Init(Master:pStream; Amin: longint; NdxFile: Pathstr);
  331. VAR Buff: tBufStream;
  332. begin
  333.    Owner:=NIL;
  334.    tEmsStream.INIT(Amin,MaxLongInt);
  335.    if Status<>StOK then FAIL {fail if not enough EMS}
  336.    else
  337.    begin
  338.       Owner:=pSortedIndex(master); {typecast our owner field to actual type}
  339.       Fname:=NdxFile;
  340.       buff.Init(Fname,stOpen,8*1024);
  341.       if Buff.Status=StOK then
  342.       begin
  343.          Seek(0);
  344.          Buff.seek(0);
  345.          CopyFrom(BUff,Buff.GetSize);
  346.          Seek(0);
  347.          cp:=0;
  348.       end
  349.       else
  350.       begin
  351.          {error Reading .NDX file!!}
  352.          Reindex; {rebuild our master list}
  353.          Owner^.Seek(0);
  354.       end;
  355.  
  356.       buff.done;
  357.  
  358.       Owner^.Seek(0);
  359.       CP:=0;
  360.    end;
  361.    DisplayProc:= OurDisplayProc;
  362. end;
  363.  
  364. Destructor NdxStream.Done;
  365. begin
  366.    flush;
  367.    tEmsStream.done;
  368. end;
  369.  
  370. {save index file to stream}
  371. Procedure NdxStream.Flush;
  372. var BUFF: tBufStream;
  373. begin
  374.    buff.Init(Fname,stCreate,8*1024);
  375.    if Buff.Status=StOK then
  376.    begin
  377.       Seek(0);
  378.       Buff.CopyFrom(Self,GetSize);
  379.    end;
  380.    buff.done;
  381. end;
  382.  
  383. Function NdxStream.EOS: Boolean;
  384. begin
  385.    EOS:=(GetPos>=GetSize);
  386. end;
  387.  
  388. {returns TRUE if found in NDX STREAM, insertion point or actual offset}
  389. {returned in ATPos}
  390. Function NdxStream.Search(Key: pIndex; VAR AtPos: LongInt): Boolean;
  391. VAR Temp: pIndex;
  392.     found: Boolean;
  393.     SearchDir: Integer;
  394.     result: Integer;
  395.     TotalPos,           {TOP}
  396.     LastSearch,         {BOTTOM}
  397.     CurrentSearch,      {MIDDLE}
  398.     SeekPos,
  399.     CurrentPos,
  400.     SavePos: LongInt;
  401.  
  402. begin
  403.    Seek(0);
  404.    CP:=0;
  405.    Searchdir:=1;
  406.    if Count>0 then
  407.       TotalPos:=Count-1 {returns total item's in Stream}
  408.    else
  409.    begin
  410.       TotalPos:=0;
  411.       SearchDir:=0;
  412.    end;
  413.    LastSearch:=0;
  414.    CurrentSearch:=(LastSearch+TotalPos) DIV 2;
  415.    Search:=FALSE;
  416.    AtPos:=GetSize; {default insert at end of stream}
  417.    Temp:=NIL;
  418.    Found:=FALSE;
  419.    While NOT FOUND and (SearchDir<>0) do
  420.    begin
  421.       SavePos:=CurrentSearch*sizeof(LongInt);
  422.       Seek(SavePos);
  423.       CP:=(SavePos DIV SizeOf(LongInt))-1;
  424.       CurrentPos:=Position;    {Track our insert position}
  425.  
  426.       Read(SeekPos,sizeof(LongInt));    {Get pos. of next object on Owner}
  427.       if SeekPos<Owner^.GetSize then    {Don't Attempt to read pas EOS!}
  428.       begin
  429.          Owner^.Seek(SeekPos);
  430.          Temp:=Pindex(Owner^.get);
  431.          if Owner^.Status = STOk then
  432.          begin
  433.              result:=Temp^.Compare(key);
  434.              Found:=(result=0);
  435.              if (Result>=0) and (currentPos<=AtPos) then
  436.                AtPos:=CurrentPos;
  437.          end
  438.          else
  439.             Owner^.Reset;    {oh oh! Something BAD happaned on our read!}
  440.  
  441.          if Temp<>NIL then
  442.            dispose(Temp,Done);
  443.       end;
  444.  
  445.       {compute Next search position}
  446.       if NOT FOUND then
  447.       begin
  448.          if Result>0 then
  449.            TotalPos:=CurrentSearch-1
  450.          else
  451.            LastSearch:=CurrentSearch+1;
  452.  
  453.          if (TotalPos<lastSearch) or (TotalPos<0) then
  454.            SearchDir:=0;
  455.       end;
  456.       CurrentSearch:=(LastSearch+TotalPos) DIV 2;
  457.    end;
  458.    Search:=Found;
  459. end;
  460.  
  461. {insert a new index key into stream, calls SEARCH to locate position of ins.}
  462. Procedure NdxStream.Insert(Key: pIndex; KeyPos: Longint);
  463. CONST
  464.     tempname = '$$$$$$$$.$$$'; {name for temporary backup file}
  465.  
  466. VAR Temp: pIndex;
  467.     filebuff,
  468.     found: Boolean;
  469.     result: Integer;
  470.     seekPos,
  471.     copysize: Longint;
  472.     pStrm: Pstream;
  473.     F: File;
  474. begin
  475.  
  476.    if Search(Key,SeekPos) then
  477.    begin {don't care, We'll ALLOW Duplicate insertions, the important thing}
  478.    end;  {is the SeekPos Variable Which tells us our position to insert at}
  479.  
  480.  
  481.    if SeekPos>=GetSize then
  482.    begin
  483.       {NOT found in file so append to end...}
  484.       seek(GetSize);
  485.       Write(KeyPos,Sizeof(LongInt));
  486.       CP:=Count-1;
  487.    end
  488.    else
  489.    begin
  490.      filebuff:=False;
  491.      Seek(SeekPos);
  492.      CopySize:=Getsize-SeekPos;
  493.      Pstrm:=NEW(pEmsStream,INIT(CopySize,maxlongint));
  494.      if (Pstrm=NIL) or (Pstrm^.Status<>StOk) then
  495.      begin
  496.        if pStrm<>NIL then
  497.          dispose(pStrm,Done);
  498.      {our Attempt to create a temporary EMS stream failed!}
  499.      {create a temporary DOS file for copying/appending...}
  500.        pStrm:=NEW(pBufStream,Init(TempName,StCreate,16*1024));
  501.        filebuff:=TRUE;
  502.      end;
  503.      if pStrm^.Status=StOK then
  504.      begin
  505.         Seek(SeekPos);
  506.         CP:=(SeekPos DIV SizeOf(LongInt))-1;
  507.         copySize:=(Getsize-SeekPos);
  508.         {copy remaining bytes to temporary file}
  509.         pStrm^.copyFrom(Self,Copysize);
  510.         pStrm^.Flush;
  511.  
  512.         {store record}
  513.         Seek(SeekPos);
  514.         Write(KeyPos,Sizeof(longInt));
  515.  
  516.         {re-append from temp file}
  517.         pStrm^.seek(0);
  518.         copyfrom(pStrm^,CopySize);
  519.  
  520.         Dispose(Pstrm,done);
  521.  
  522.         {erase temporary file if dos bufferred}
  523.         if FileBuff then
  524.         begin
  525.             {$I-}
  526.             assign(F,TempName);
  527.             erase(F);
  528.             {$I+}
  529.             if IoResult<>0 then begin; end; {don't really care (much!)}
  530.         end;
  531.      end;
  532.    end;
  533. End;
  534.  
  535. {rebuilds our index order, called if NDX file doesn't exist or at}
  536. {users request, benchmark: 6000 items in 2+ minutes}
  537. Procedure NdxStream.Reindex;
  538. VAR Temp: pIndex;
  539.     StartPos,
  540.     current,
  541.     P,Result: Longint;
  542.     X,Y: Byte;
  543. begin
  544.    writeln;
  545.    X:=WhereX;
  546.    Y:=WhereY;
  547.    Temp:=NIL;
  548.    Seek(0);
  549.    CP:=0;
  550.    Truncate;  {dispose of any previous data}
  551.    Owner^.Seek(0); {reposition master stream}
  552.    While NOT Owner^.EOS do
  553.    begin
  554.       displayProc(CP,X,Y);
  555.       StartPos:=Owner^.Position;
  556.       Temp:=pIndex(Owner^.Get);
  557.       Current:=Owner^.Position;
  558.       if Owner^.Status=StOk then
  559.       begin
  560.          Insert(temp,StartPos);
  561.          if Temp<>NIL then
  562.          begin
  563.             dispose(Temp,Done);
  564.             Temp:=NIL;
  565.          end;
  566.       end;
  567.       Owner^.Seek(Current);
  568.    end;
  569. end;
  570.  
  571. {returns number of items in index list}
  572. Function NdxStream.Count: LongInt;
  573. begin
  574.    Count:=Size DIV SizeOf(LongInt);
  575. end;
  576.  
  577. Function NdxStream.AT: Longint;
  578. VAR p: Longint;
  579. begin
  580.    P:=CP*SizeOf(LongInt);
  581.    if P>=Size then
  582.       AT:=Owner^.GetSize
  583.    else
  584.    begin
  585.       seek(P);
  586.       Read(P,SizeOf(LongInt));
  587.       AT:=P;
  588.    end;
  589. end;
  590.  
  591. Procedure NdxStream.POS(P: Longint);
  592. VAR L: LongInt;
  593.     I: Longint;
  594.     Top, Middle,Bottom: Longint;
  595. begin
  596.    seek(0);
  597.    Cp:=0;
  598.    L:=-1;
  599.    I:=0;
  600.    Bottom:=0;
  601.    Top:=Count;
  602.    middle:=Top DIV 2;
  603.    if Size>0 then
  604.    While (Bottom<=Top) and (L<>P) do
  605.    begin
  606.       Cp:=Middle;
  607.       Seek(Middle*sizeOf(LongINt));
  608.  
  609.       Read(L,SizeOf(LongINt));
  610.  
  611.       if P<L then
  612.          Top:=Middle-1
  613.       else Bottom:=Middle+1;
  614.       Middle:=(Bottom+Top) DIV 2
  615.    end;
  616. end;
  617.  
  618. Procedure NDXStream.NextPos;
  619. begin
  620.    if CP<=count then
  621.      INC(CP)
  622.    else Owner^.Seek(Owner^.GetSize);
  623. end;
  624.  
  625. end.
  626.  
  627.